1. Field of the Invention
The present invention relates to communications systems. More specifically, the present invention relates to methods and apparatus for routing data packets through a packet communications network.
While the present invention is described herein with reference to illustrative embodiments for particular applications, it should be understood that the invention is not limited thereto. Those having ordinary skill in the art and access to the teachings provided herein will recognize additional modifications, applications and embodiments within the scope thereof and additional fields in which the present invention would be of significant utility.
2. Description of the Related Art
Packet communication networks are known in the art and can support a central control site that is used to control and monitor a plurality of remote sites. The central control site can be comprised of a computer to perform controlling and monitoring functions. The remote sites can include microprocessor based systems that perform monitoring and control of local equipment. An example of a system that is suitable for incorporating a packet communication network is a traffic light system. The control function of the central control site might be the coordinated timing of multiple traffic lights in an area while the control function of the remote site might be the control of a single traffic light.
The function of a packet communication network is to support the transmission of binary data or messages between computers. The messages are routed through a network where a network is defined as an arbitrary arrangement of radios. Routing of the messages is accomplished through available radio frequency (RF) links between points in the network. Each radio within the packet communication network maintains a data base that allows the radio to relay all received messages to a further destination along the most direct path. The routing of a message by a radio along the path serves as a relay since the message is received, processed and retransmitted to a further radio destination. This function is referred to as store and forward relaying and is accomplished by a method known as the Minimum Hop Approach. The Minimum Hop Approach involves an algorithm that is employed to determine the shortest path between two points, e.g., network radios. The Minimum Hop Approach and the associated algorithm are known in the art and can be found in a textbook entitled Telecommunication Networks by Mischa Schwartz published by Addison-Wesley, copyright 1987.
In general, packet communication networks are a form of data communications in which data packets are routed between central control and a remote station. Error checksum and receipt verification methods can also be incorporated. Several methods of data packet routing are known in the art. According to one method, the address in the header of the data packet is used as an index to a directory of packet routing lists. Packet routing lists must be prepared with knowledge about the location of each radio in the network. Each radio is identified by a header code or bit and a packet routing list consists of an ordered list of radio header bits or call signs. Directory-based routing techniques require continued maintenance and communication of the network interconnectivity information employed in the directory. Each of these functions drains the resources of the network and can become unmanageable in a large network.
Another basic technique of routing data packets through packet communication networks is nondirectory-based. In nondirectory-based routing, the complexities associated with routing techniques are avoided. The construction of the network is simplified since there is no connectivity information. However, nondirectory-based routing techniques do not permit network parameter optimization as do the directory-based routing techniques.
Two basic architectures of packet communication networks are known. In an earlier design, a central control computer transmitted data packets to and received monitoring information from the individual remote radios. A major problem associated with this network is time limitation. The data packet must be received and processed, the most direct path to a destination radio must be identified and then the data packet must be retransmitted to hundreds of remote radios at the rate of one message at a time once per second. Because of this delay, packet communication networks are unable to support rapid communications systems.
In a more current design, packet communication networks are optimized for communications in which any remote radio can communicate with any other remote radio. Further, current designs provide the ability to network communications over a large geographical area with line-of-sight remote radios. However, several disadvantages exist with the current design of packet communication networks. First, the radio design requires on the order of one second per relay hop to transmit a data packet from one remote radio to another. Second, each message of the data packet must be handled as a separate transaction, e.g., on a message-by-message basis. In support of the control and monitoring functions, each message from the central control computer must be handled independently from the other messages. Third, the radio is unable to concatenate multiple messages into a single packet where each message has a different destination.
Radio technology employed in the past exhibited very slow switching times when transferring between the receive and transmit modes. The switching times of analog components such as a transceiver were on the order of many milliseconds. Therefore, tens-to-hundreds of milliseconds of radio switching time were lost during the relaying of the data packets. Spread spectrum radio technology is now commercially available. This technology is provided with improved radio switching times on the order of one millisecond. Notwithstanding the faster switching times available in the advanced radio technology, the previously described problems continue to inhibit the performance of packet communication networks.
Thus, there is a need in the art for improvements in routing data packets through packet communication networks.